// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 此文件实现无符号多精度整数（自然
// 数字）。它们是实现带符号整数、有理数和浮点数的构造块。
// 
// 注意：此实现依赖于函数“alias”
// 该函数假定（nat）片容量从未更改过
// 无3操作数片表达式。如果
// 发生更改，则需要更新别名以确保正确性。

package big

import (
	"encoding/binary"
	"math/bits"
	"math/rand"
	"sync"
)

// 
// 
// x=x[n-1]*B^（n-1）+x[n-2]*B^（n-2）+x[1]*_B+x[0]
// 
// 其中0<=x[i]<_B和0<=i<n存储在长度为n的切片中，
// 以数字x[i]作为切片元素。
// 
// 如果切片不包含前导0位，则一个数字将被规范化。
// 在算术运算期间，可能会出现非规范化值，但在返回最终结果之前，这些值始终是
// 的标准化值。0的标准化
// 表示为空或零切片（长度=0）。
// 
type nat []Word

var (
	natOne  = nat{1}
	natTwo  = nat{2}
	natFive = nat{5}
	natTen  = nat{10}
)

func (z nat) clear() {
	for i := range z {
		z[i] = 0
	}
}

func (z nat) norm() nat {
	i := len(z)
	for i > 0 && z[i-1] == 0 {
		i--
	}
	return z[0:i]
}

func (z nat) make(n int) nat {
	if n <= cap(z) {
		return z[:n] // reuse z 
	}
	if n == 1 {
		// 大多数NAT从小处开始，一直保持这种状态；不要过度分配。
		return make(nat, 1)
	}
	// 为e选择一个好的值会对性能产生显著影响
	// 因为它增加了值可重用的机会。
	const e = 4 // 额外容量
	return make(nat, n, n+e)
}

func (z nat) setWord(x Word) nat {
	if x == 0 {
		return z[:0]
	}
	z = z.make(1)
	z[0] = x
	return z
}

func (z nat) setUint64(x uint64) nat {
	// 单字值
	if w := Word(x); uint64(w) == x {
		return z.setWord(w)
	}
	// 双字值
	z = z.make(2)
	z[1] = Word(x >> 32)
	z[0] = Word(x)
	return z
}

func (z nat) set(x nat) nat {
	z = z.make(len(x))
	copy(z, x)
	return z
}

func (z nat) add(x, y nat) nat {
	m := len(x)
	n := len(y)

	switch {
	case m < n:
		return z.add(y, x)
	case m == 0:
		// n==0，因为m>=n；结果是0 
		return z[:0]
	case n == 0:
		// 结果是x 
		return z.set(x)
	}
	// m>0 

	z = z.make(m + 1)
	c := addVV(z[0:n], x, y)
	if m > n {
		c = addVW(z[n:m], x[n:], c)
	}
	z[m] = c

	return z.norm()
}

func (z nat) sub(x, y nat) nat {
	m := len(x)
	n := len(y)

	switch {
	case m < n:
		panic("underflow")
	case m == 0:
		// n==0，因为m>=n；结果是0 
		return z[:0]
	case n == 0:
		// 结果是x 
		return z.set(x)
	}
	// m>0 

	z = z.make(m)
	c := subVV(z[0:n], x, y)
	if m > n {
		c = subVW(z[n:], x[n:], c)
	}
	if c != 0 {
		panic("underflow")
	}

	return z.norm()
}

func (x nat) cmp(y nat) (r int) {
	m := len(x)
	n := len(y)
	if m != n || m == 0 {
		switch {
		case m < n:
			r = -1
		case m > n:
			r = 1
		}
		return
	}

	i := m - 1
	for i > 0 && x[i] == y[i] {
		i--
	}

	switch {
	case x[i] < y[i]:
		r = -1
	case x[i] > y[i]:
		r = 1
	}
	return
}

func (z nat) mulAddWW(x nat, y, r Word) nat {
	m := len(x)
	if m == 0 || y == 0 {
		return z.setWord(r) // 结果是r 
	}
	// m>0 

	z = z.make(m + 1)
	z[m] = mulAddVWW(z[0:m], x, y, r)

	return z.norm()
}

// 基本公式将x和y相乘，并将结果保留在z中。
// 非规范化的结果放在z[0:len（x）+len y）]。
func basicMul(z, x, y nat) {
	z[0 : len(x)+len(y)].clear() // 初始化z 
	for i, d := range y {
		if d != 0 {
			z[len(x)+i] = addMulVVW(z[i:i+len(x)], x, d)
		}
	}
}

// 蒙哥马利计算z mod m=x*y*2**（-n*_W）mod m，
// 假设k=-1/m mod 2**_W。
// z用于存储返回的结果；
// z不能使用别名x、y或m。
// 参见Gueron，“模块求幂的有效软件实现”。
// https:
// 在那篇论文的术语中，这是一个“几乎蒙哥马利乘法”：
// x和y需要满足0<=z<2**（n*_W），然后结果
// z保证满足0<=z<2**（n*_W），但它可能不是<m。
func (z nat) montgomery(x, y, m nat, k Word, n int) nat {
	// 这段代码假设x，y，m都是相同的长度，n.
	// （addMulVVW和for循环要求）。
	// 它还假设x，y已经被减少到m，
	// 否则结果将不会被适当减少。
	if len(x) != n || len(y) != n || len(m) != n {
		panic("math/big: mismatched montgomery number lengths")
	}
	z = z.make(n * 2)
	z.clear()
	var c Word
	for i := 0; i < n; i++ {
		d := y[i]
		c2 := addMulVVW(z[i:n+i], x, d)
		t := z[i] * k
		c3 := addMulVVW(z[i:n+i], m, t)
		cx := c + c2
		cy := cx + c3
		z[n+i] = cy
		if cx < c2 || cy < c3 {
			c = 1
		} else {
			c = 0
		}
	}
	if c != 0 {
		subVV(z[:n], z[n:], m)
	} else {
		copy(z[:n], z[n:])
	}
	return z[:n]
}

// z的快速版本[0:n+n>>1]。添加（z[0:n+n>>1]，x[0:n]）不带边界检查。
// 考虑了可读性——不要在卡拉祖巴之外使用。
func karatsubaAdd(z, x nat, n int) {
	if c := addVV(z[0:n], z, x); c != 0 {
		addVW(z[n:n+n>>1], z[n:], c)
	}
}

// 类似于karatsubaAdd，但会减法。
func karatsubaSub(z, x nat, n int) {
	if c := subVV(z[0:n], z, x); c != 0 {
		subVW(z[n:n+n>>1], z[n:], c)
	}
}

// 比karatsubaThreshold短的操作数使用
// “小学”乘法相乘；对于较长的操作数，使用Karatsuba算法
// 。
var karatsubaThreshold = 40 // 通过校准测试计算。go 

// karatsuba将x和y相乘，并将结果保留在z中。
// x和y必须具有相同的长度n，n必须是
// 2的幂。结果向量z必须具有len（z）>=6*n。
// 将（非规范化）结果放置在z[0:2*n]中。
func karatsuba(z, x, y nat) {
	n := len(y)

	// 如果数字是奇数或小的，则切换到基本乘法。
	// （n始终是偶数，如果karatsubaThreshold是偶数，但要保守）
	if n&1 != 0 || n < karatsubaThreshold || n < 2 {
		basicMul(z, x, y)
		return
	}
	// n&1==0&&n>=karatsubaThreshold&&n>=2 

	// Karatsuba乘法是基于这样一个观察：
	// =y1*b+y0 
	// 
	// 产品x*y可以通过三种产品z2、z1、z1、Z3获得，z0 
	// 代替4:
	// 
	// x*y=x1*y1*b*b+（x1*y0+x0*y1）*b+x0*y0 
	// /=z2*b*b+z1*b+z0 
	// 
	// yd=y0-y1 
	// 
	// z1=xd*yd+z2+z0 
	// /=（x1-x0）*（y0-y1）+z2+z0 
	// /=x1*y0-x1*y1-x0*y0+x0*y1+z2+z0 
	// /=x1*y0-z2-z0+x0*y1+z0 
	// /=x1*y0+x0*y1 

	// 拆分x，y为“数字”
	n2 := n >> 1              // n2>=1 
	x1, x0 := x[n2:], x[0:n2] // x=x1*b+y0 
	y1, y0 := y[n2:], y[0:n2] // y=y1*b+y0 

	// z用于结果和临时存储：
	// 
	// /6*n5*n4*n3*n2*n1*n0*n
	// z=[z2 copy | z0 copy*yd
	// z片段，其长度（至少）为调用方z的一半。

	// compute z0和z2，结果在z 
	karatsuba(z, x0, y0)     // z0=x0*y0 
	karatsuba(z[n:], x1, y1) // z2=x1*y1 

	// compute xd（或出现下溢时的负值）
	xd := z[2*n : 2*n+n2]
	if subVV(xd, x1, x0) != 0 { // x1-x0 
		s = -s
		subVV(xd, x0, x1) // x0-x1 
	}

	// 计算yd（或出现下溢时的负值）
	yd := z[2*n+n2 : 3*n]
	if subVV(yd, y0, y1) != 0 { // y0-y1 
		s = -s
		subVV(yd, y1, y0) // y1-y0 
	}

	// p=（x1-x0）*（y0-y1）==x1*y0-x1*y1 x0-x1*y1z2:z0 
	p := z[n*3:]
	karatsuba(p, xd, yd)

	// （可以使用z的上半部分，因为我们已经完成了递归）
	r := z[n*4:]
	copy(r, z[:n*2])

	// /将所有部分积相加
	// 
	// 2*n0 
	// z=[z2 | z0]
	// +[z0]
	karatsubaAdd(z[n2:], r, n)
	karatsubaAdd(z[n2:], r[n:], n)
	if s > 0 {
		karatsubaAdd(z[n2:], p, n)
	} else {
		karatsubaSub(z[n2:], p, n)
	}
}

// 注意：alias假设nat值的基础数组
// 的容量不会改变；i、 e.这段代码中没有三个操作数的切片表达式（或者更糟的是，基于反射的操作也有相同的效果）。
func alias(x, y nat) bool {
	return cap(x) > 0 && cap(y) > 0 && &x[0:cap(x)][cap(x)-1] == &y[0:cap(y)][cap(y)-1]
}

// addAt实现z+=x<<（_W*i）；z必须足够长。
// （我们不使用nat.add，因为我们需要z保持不变
// 切片，并且我们不需要在每次加法后对z进行规格化）
func addAt(z, x nat, i int) {
	if n := len(x); n > 0 {
		if c := addVV(z[i:i+n], z[i:], x); c != 0 {
			j := i + n
			if j < len(z) {
				addVW(z[j:], z[j:], c)
			}
		}
	}
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

// karatsubaLen计算最大k<=n的近似值，这样
// k=p<<i，对于一个数字p<=阈值和一个i>=0。因此，在
// 结果是可以重复除以2的最大数。
// 成为阈值之前，
func karatsubaLen(n, threshold int) int {
	i := uint(0)
	for n > threshold {
		n >>= 1
		i++
	}
	return n << i
}

func (z nat) mul(x, y nat) nat {
	m := len(x)
	n := len(y)

	switch {
	case m < n:
		return z.mul(y, x)
	case m == 0 || n == 0:
		return z[:0]
	case n == 1:
		return z.mulAddWW(x, y[0], 0)
	}
	// m>=n>1 

	// 确定z是否可以重用
	if alias(z, x) || alias(z, y) {
		z = nil // z是x或y的别名-不能重用
	}

	// 如果数字很小，请使用基本乘法
	if n < karatsubaThreshold {
		z = z.make(m + n)
		basicMul(z, x, y)
		return z.norm()
	}

	k := karatsubaLen(n, karatsubaThreshold)

	karatsuba(z, x0, y0)
	z = z[0 : m+n]  // z具有最终长度，但可能不完整
	z[2*k:].clear() // z的上半部分是垃圾（2*k<=m+n，因为k<=n<=m）

	// 如果xh！=0或yh！=0，将缺少的项添加到z。对于
	// 
	// xh=xi*b^i+…+CFDEG 
	if k < n || m != n {
		tp := getNat(3 * k)
		t := *tp

		x0 := x0.norm()
		addAt(z, t, k)

		y0 := y0.norm()
		for i := k; i < len(x); i += k {
			xi := x[i:]
			if len(xi) > k {
				xi = xi[:k]
			}
			xi = xi.norm()
			t = t.mul(xi, y0)
			addAt(z, t, i)
			t = t.mul(xi, y1)
			addAt(z, t, i+k)
		}

		putNat(tp)
	}

	return z.norm()
}

// basicSqr设置z=x*x，比basicMul 
// 快大约2倍，但由于开销，对于小参数，速度较慢。
// 要求：len（x）>0，len（z）==2*len（x）
// 将（非规范化）结果放置在z中。
func basicSqr(z, x nat) {
	n := len(x)
	tp := getNat(2 * n)
	t := *tp // 用于保存产品的临时变量
	t.clear()
	z[1], z[0] = mulWW(x[0], x[0]) // 初始正方形
	for i := 1; i < n; i++ {
		d := x[i]
		// z收集正方形x[i]*x[i]
		z[2*i+1], z[2*i] = mulWW(d, d)
		// t收集产品x[i]*x[j]，其中j<i 
		t[2*i] = addMulVVW(t[i:2*i], x[0:i], d)
	}
	t[2*n-1] = shlVU(t[1:2*n-1], t[1:2*n-1], 1) // 将j<i产品
	addVV(z, z, t)                              // 组合结果
	putNat(tp)
}

// karatsubaSqr平方x，并将结果留在z中。
// len（x）必须是2的幂，且len（z）>=6*len（x）。
// 将（非标准化）结果放在z[0:2*len（x）]中。
// 
// z的算法和布局与karatsuba相同。
func karatsubaSqr(z, x nat) {
	n := len(x)

	if n&1 != 0 || n < karatsubaSqrThreshold || n < 2 {
		basicSqr(z[:2*n], x)
		return
	}

	n2 := n >> 1
	x1, x0 := x[n2:], x[0:n2]

	karatsubaSqr(z, x0)
	karatsubaSqr(z[n:], x1)

	// s=符号（xd*yd）=-1表示xd！=0; s==1表示xd==0 
	xd := z[2*n : 2*n+n2]
	if subVV(xd, x1, x0) != 0 {
		subVV(xd, x0, x1)
	}

	p := z[n*3:]
	karatsubaSqr(p, xd)

	r := z[n*4:]
	copy(r, z[:n*2])

	karatsubaAdd(z[n2:], r, n)
	karatsubaAdd(z[n2:], r[n:], n)
	karatsubaSub(z[n2:], p, n) // s==1表示p！=0; s==1表示p==0 
}

// 使用
// “小学”乘法对小于基本QRThreshold的操作数进行平方运算；对于比karatsubaSqrThreshold 
// 长的操作数，我们使用为x==y优化的Karatsuba算法。
var basicSqrThreshold = 20      // 通过calibrate_test计算。转到
var karatsubaSqrThreshold = 260 // 通过校准测试计算。go 

// z=x*x 
func (z nat) sqr(x nat) nat {
	n := len(x)
	switch {
	case n == 0:
		return z[:0]
	case n == 1:
		d := x[0]
		z = z.make(2)
		z[1], z[0] = mulWW(d, d)
		return z.norm()
	}

	if alias(z, x) {
		z = nil // z是x的别名-不能重用
	}

	if n < basicSqrThreshold {
		z = z.make(2 * n)
		basicMul(z, x, x)
		return z.norm()
	}
	if n < karatsubaSqrThreshold {
		z = z.make(2 * n)
		basicSqr(z, x)
		return z.norm()
	}

	// 使用为x==y优化的Karatsuba乘法。
	// z的算法和布局与mul相同。

	// z=（x1*b+x0）^2=x1^2*b^2+2*x1*x0*b+x0^2 

	k := karatsubaLen(n, karatsubaSqrThreshold)

	x0 := x[0:k]
	z = z.make(max(6*k, 2*n))
	karatsubaSqr(z, x0) // z=x0^2 
	z = z[0 : 2*n]
	z[2*k:].clear()

	if k < n {
		tp := getNat(2 * k)
		t := *tp
		x0 := x0.norm()
		x1 := x[k:]
		t = t.mul(x0, x1)
		addAt(z, t, k)
		addAt(z, t, k) // z=2*x1*x0*b+x0^2 
		t = t.sqr(x1)
		addAt(z, t, 2*k) // z=x1^2*b^2+2*x1*x0*b+x0^2 
		putNat(tp)
	}

	return z.norm()
}

// MULTRANGE计算
// 范围内所有无符号整数的乘积。如果a>b（空范围），结果为1。
func (z nat) mulRange(a, b uint64) nat {
	switch {
	case a == 0:
		// 剪切长距离短距离（优化）
		return z.setUint64(0)
	case a > b:
		return z.setUint64(1)
	case a == b:
		return z.setUint64(a)
	case a+1 == b:
		return z.mul(nat(nil).setUint64(a), nat(nil).setUint64(b))
	}
	m := (a + b) / 2
	return z.mul(nat(nil).mulRange(a, m), nat(nil).mulRange(m+1, b))
}

// getNat返回len n的*nat。内容不能为零。
// 池持有*nat以避免转换到接口{}时分配。
func getNat(n int) *nat {
	var z *nat
	if v := natPool.Get(); v != nil {
		z = v.(*nat)
	}
	if z == nil {
		z = new(nat)
	}
	*z = z.make(n)
	return z
}

func putNat(x *nat) {
	natPool.Put(x)
}

var natPool sync.Pool

// x的长度（以位为单位）。x必须标准化。
func (x nat) bitLen() int {
	if i := len(x) - 1; i >= 0 {
		return i*_W + bits.Len(uint(x[i]))
	}
	return 0
}

// trailingZeroBits返回连续最低有效零的数量
// x的位。
func (x nat) trailingZeroBits() uint {
	if len(x) == 0 {
		return 0
	}
	var i uint
	for x[i] == 0 {
		i++
	}
	// x[i]！=0 
	return i*_W + uint(bits.TrailingZeros(uint(x[i])))
}

func same(x, y nat) bool {
	return len(x) == len(y) && len(x) > 0 && &x[0] == &y[0]
}

// z=x<s 
func (z nat) shl(x nat, s uint) nat {
	if s == 0 {
		if same(z, x) {
			return z
		}
		if !alias(z, x) {
			return z.set(x)
		}
	}

	m := len(x)
	if m == 0 {
		return z[:0]
	}
	// m>0 

	n := m + int(s/_W)
	z = z.make(n + 1)
	z[n] = shlVU(z[n-m:n], x, s%_W)
	z[0 : n-m].clear()

	return z.norm()
}

// z=x>>s 
func (z nat) shr(x nat, s uint) nat {
	if s == 0 {
		if same(z, x) {
			return z
		}
		if !alias(z, x) {
			return z.set(x)
		}
	}

	m := len(x)
	n := m - int(s/_W)
	if n <= 0 {
		return z[:0]
	}
	// n>0 

	z = z.make(n)
	shrVU(z, x[m-n:], s%_W)

	return z.norm()
}

func (z nat) setBit(x nat, i uint, b uint) nat {
	j := int(i / _W)
	m := Word(1) << (i % _W)
	n := len(x)
	switch b {
	case 0:
		z = z.make(n)
		copy(z, x)
		if j >= n {
			// 无需增长
			return z
		}
		z[j] &^= m
		return z.norm()
	case 1:
		if j >= n {
			z = z.make(j + 1)
			z[n:].clear()
		} else {
			z = z.make(n)
		}
		copy(z, x)
		z[j] |= m
		// 无需规范化
		return z
	}
	panic("set bit is not 0 or 1")
}

// 位返回第i位的值，lsb==0位。
func (x nat) bit(i uint) uint {
	j := i / _W
	if j >= uint(len(x)) {
		return 0
	}
	// 0<=j<len（x）
	return uint(x[j] >> (i % _W) & 1)
}

// 如果
// 中有1位，则粘性返回1，否则返回0。
func (x nat) sticky(i uint) uint {
	j := i / _W
	if j >= uint(len(x)) {
		if len(x) == 0 {
			return 0
		}
		return 1
	}
	// 0<=j<len（x）
	for _, x := range x[:j] {
		if x != 0 {
			return 1
		}
	}
	if x[j]<<(_W-i%_W) != 0 {
		return 1
	}
	return 0
}

func (z nat) and(x, y nat) nat {
	m := len(x)
	n := len(y)
	if m > n {
		m = n
	}
	// m<=n 

	z = z.make(m)
	for i := 0; i < m; i++ {
		z[i] = x[i] & y[i]
	}

	return z.norm()
}

func (z nat) andNot(x, y nat) nat {
	m := len(x)
	n := len(y)
	if n > m {
		n = m
	}
	// m>=n 

	z = z.make(m)
	for i := 0; i < n; i++ {
		z[i] = x[i] &^ y[i]
	}
	copy(z[n:m], x[n:m])

	return z.norm()
}

func (z nat) or(x, y nat) nat {
	m := len(x)
	n := len(y)
	s := x
	if m < n {
		n, m = m, n
		s = y
	}
	// m>=n 

	z = z.make(m)
	for i := 0; i < n; i++ {
		z[i] = x[i] | y[i]
	}
	copy(z[n:m], s[n:m])

	return z.norm()
}

func (z nat) xor(x, y nat) nat {
	m := len(x)
	n := len(y)
	s := x
	if m < n {
		n, m = m, n
		s = y
	}
	// m>=n 

	z = z.make(m)
	for i := 0; i < n; i++ {
		z[i] = x[i] ^ y[i]
	}
	copy(z[n:m], s[n:m])

	return z.norm()
}

// random在[0..limit]中创建一个随机整数，如果
// 可能，则使用z中的空格。n是limit的位长度。
func (z nat) random(rand *rand.Rand, limit nat, n int) nat {
	if alias(z, limit) {
	}
	z = z.make(len(limit))

	bitLengthOfMSW := uint(n % _W)
	if bitLengthOfMSW == 0 {
		bitLengthOfMSW = _W
	}
	mask := Word((1 << bitLengthOfMSW) - 1)

	for {
		switch _W {
		case 32:
			for i := range z {
				z[i] = Word(rand.Uint32())
			}
		case 64:
			for i := range z {
				z[i] = Word(rand.Uint32()) | Word(rand.Uint32())<<32
			}
		default:
			panic("unknown word size")
		}
		z[len(limit)-1] &= mask
		if z.cmp(limit) < 0 {
			break
		}
	}

	return z.norm()
}

// 否则它会将z设置为x**y。结果是z的值。
func (z nat) expNN(x, y, m nat) nat {
	if alias(z, x) || alias(z, y) {
		// 我们不能允许对x或y进行就地修改。
		z = nil
	}

	// x**y mod 1==0 
	if len(m) == 1 && m[0] == 1 {
		return z.setWord(0)
	}
	// m==0 | m>1 

	// x**0==1 
	if len(y) == 0 {
		return z.setWord(1)
	}
	// y>0 

	// x**1 mod m==x mod和模量一样长。
	if len(y) == 1 && y[0] == 1 && len(m) != 0 {
		_, z = nat(nil).div(z, x, m)
		return z
	}

	if len(m) != 0 {
		z = z.make(len(m))
	}
	z = z.set(x)

	// 如果基是非平凡的且指数很大，我们使用
	// 4位加窗指数运算。这涉及到预先计算14个值
	// （x^2…x^15），但随后将乘法减数减少为
	// 3。即使对于32位指数，这也会减少
	// 操作的数量。对奇数模使用蒙哥马利方法。
	if x.cmp(natOne) > 0 && len(y) > 1 && len(m) > 0 {
		if m[0]&1 == 1 {
			return z.expNNMontgomery(x, y, m)
		}
		return z.expNNWindowed(x, y, m)
	}

	v := y[len(y)-1] // v>0因为y是标准化的，y>0 
	shift := nlz(v) + 1
	v <<= shift
	var q nat

	const mask = 1 << (_W - 1)

	// 我们逐个遍历指数的位。每次我们看到一点，我们就会变方，从而使功率加倍。如果位是1，我们也乘以x，因此幂加1。

	w := _W - int(shift)
	// zz和r用于避免在mul和div中分配为
	// 否则参数将被忽略。
	var zz, r nat
	for j := 0; j < w; j++ {
		zz = zz.sqr(z)
		zz, z = z, zz

		if v&mask != 0 {
			zz = zz.mul(z, x)
			zz, z = z, zz
		}

		if len(m) != 0 {
			zz, r = zz.div(r, z, m)
			zz, r, q, z = q, z, zz, r
		}

		v <<= 1
	}

	for i := len(y) - 2; i >= 0; i-- {
		v = y[i]

		for j := 0; j < _W; j++ {
			zz = zz.sqr(z)
			zz, z = z, zz

			if v&mask != 0 {
				zz = zz.mul(z, x)
				zz, z = z, zz
			}

			if len(m) != 0 {
				zz, r = zz.div(r, z, m)
				zz, r, q, z = q, z, zz, r
			}

			v <<= 1
		}
	}

	return z.norm()
}

// expNNWindowed使用固定的4位窗口计算x**y mod m。
func (z nat) expNNWindowed(x, y, m nat) nat {
	// zz和r用于避免在mul和div中进行分配，否则
	// 参数将使用别名。
	var zz, r nat

	const n = 4
	// 幂[i]包含x^i。
	var powers [1 << n]nat
	powers[0] = natOne
	powers[1] = x
	for i := 2; i < 1<<n; i += 2 {
		p2, p, p1 := &powers[i/2], &powers[i], &powers[i+1]
		*p = p.sqr(*p2)
		zz, r = zz.div(r, *p, m)
		*p, r = r, *p
		*p1 = p1.mul(*p, x)
		zz, r = zz.div(r, *p1, m)
		*p1, r = r, *p1
	}

	z = z.setWord(1)

	for i := len(y) - 1; i >= 0; i-- {
		yi := y[i]
		for j := 0; j < _W; j += n {
			if i != len(y)-1 || j != 0 {
				// 展开循环以获得显著性能
				// 增益。使用crypto/rsa 
				// 中的go test-bench=“.*”，在进行更改之前检查性能。
				zz = zz.sqr(z)
				zz, z = z, zz
				zz, r = zz.div(r, z, m)
				z, r = r, z

				zz = zz.sqr(z)
				zz, z = z, zz
				zz, r = zz.div(r, z, m)
				z, r = r, z

				zz = zz.sqr(z)
				zz, z = z, zz
				zz, r = zz.div(r, z, m)
				z, r = r, z

				zz = zz.sqr(z)
				zz, z = z, zz
				zz, r = zz.div(r, z, m)
				z, r = r, z
			}

			zz = zz.mul(z, powers[yi>>(_W-n)])
			zz, z = z, zz
			zz, r = zz.div(r, z, m)
			z, r = r, z

			yi <<= n
		}
	}

	return z.norm()
}

// expNNMontgomery使用固定的4位窗口计算x**y mod m。
// 使用蒙哥马利表示法。我们希望x和m的长度相等。
func (z nat) expNNMontgomery(x, y, m nat) nat {
	numWords := len(m)

	// 如果x>=m只要len（x）==len（m）就可以了。
	if len(x) > numWords {
		_, x = nat(nil).div(nil, x, m)
		// 注意：现在len（x）<=numWords，不保证==。
	}
	if len(x) < numWords {
		rr := make(nat, numWords)
		copy(rr, x)
		x = rr
	}

	// 理想情况下，预计算将在外部执行，并重复使用
	// k0=-m**-1 mod 2**.\W.算法来源：杜马，J.G.“关于牛顿-拉斐逊
	// 乘性逆模素数幂的迭代”。
	k0 := 2 - m[0]
	t := m[0] - 1
	for i := 1; i < _W; i <<= 1 {
		t *= t
		k0 *= (t + 1)
	}
	k0 = -k0

	// RR=2**（2*_W*len（m））mod m 
	RR := nat(nil).setWord(1)
	zz := nat(nil).shl(RR, uint(2*numWords*_W))
	_, RR = nat(nil).div(RR, zz, m)
	if len(RR) < numWords {
		zz = zz.make(numWords)
		copy(zz, RR)
		RR = zz
	}
	// one=1，长度与m 
	one := make(nat, numWords)
	one[0] = 1

	const n = 4
	// 幂[i]包含x^i 
	var powers [1 << n]nat
	powers[0] = powers[0].montgomery(one, RR, m, k0, numWords)
	powers[1] = powers[1].montgomery(x, RR, m, k0, numWords)
	for i := 2; i < 1<<n; i++ {
		powers[i] = powers[i].montgomery(powers[i-1], powers[1], m, k0, numWords)
	}

	// 初始化z=1（蒙哥马利1）
	z = z.make(numWords)
	copy(z, powers[0])

	zz = zz.make(numWords)

	// 相同的加窗指数，但使用蒙哥马利乘法
	for i := len(y) - 1; i >= 0; i-- {
		yi := y[i]
		for j := 0; j < _W; j += n {
			if i != len(y)-1 || j != 0 {
				zz = zz.montgomery(z, z, m, k0, numWords)
				z = z.montgomery(zz, zz, m, k0, numWords)
				zz = zz.montgomery(z, z, m, k0, numWords)
				z = z.montgomery(zz, zz, m, k0, numWords)
			}
			zz = zz.montgomery(z, powers[yi>>(_W-n)], m, k0, numWords)
			z, zz = zz, z
			yi <<= n
		}
	}
	// 转换为正则数
	zz = zz.montgomery(z, one, m, k0, numWords)

	// 最后一次缩减，以防万一。
	// 见golang。org/issue/13907。
	if zz.cmp(m) >= 0 {
		// 常见情况是m具有高位集；在这种情况下，
		// 因为zz的长度与m相同，所以只需要
		// 将m的倍数去掉。减去就行了。
		// 我们认为减法一般来说应该足够了，
		// 所以无条件地这样做，但是仔细检查，
		// 以防我们的信念是错误的。
		// 预计无法联系到div。
		zz = zz.sub(zz, m)
		if zz.cmp(m) >= 0 {
			_, zz = nat(nil).div(nil, zz, m)
		}
	}

	return zz.norm()
}

// 字节使用大端编码将z的值写入buf。
// z的值编码在切片buf[i:]中。如果z 
// 的值不能用buf表示，则字节数为零。结果返回buf开头未使用的
// 字节数i。
func (z nat) bytes(buf []byte) (i int) {
	i = len(buf)
	for _, d := range z {
		for j := 0; j < _S; j++ {
			i--
			if i >= 0 {
				buf[i] = byte(d)
			} else if byte(d) != 0 {
				panic("math/big: buffer too small to fit value")
			}
			d >>= 8
		}
	}

	if i < 0 {
		i = 0
	}
	for i < len(buf) && buf[i] == 0 {
		i++
	}

	return
}

// bigEndianWord返回被解释为bigendian编码的单词值的buf的内容。
func bigEndianWord(buf []byte) Word {
	if _W == 64 {
		return Word(binary.BigEndian.Uint64(buf))
	}
	return Word(binary.BigEndian.Uint32(buf))
}

// setBytes将buf解释为一个大端无符号
// 整数的字节，将z设置为该值，并返回z。
func (z nat) setBytes(buf []byte) nat {
	z = z.make((len(buf) + _S - 1) / _S)

	i := len(buf)
	for k := 0; i >= _S; k++ {
		z[k] = bigEndianWord(buf[i-_S : i])
		i -= _S
	}
	if i > 0 {
		var d Word
		for s := uint(0); i > 0; s += 8 {
			d |= Word(buf[i-1]) << s
			i--
		}
		z[len(z)-1] = d
	}

	return z.norm()
}

// sqrt sets z=⌊√十、⌋ 
func (z nat) sqrt(x nat) nat {
	if x.cmp(natOne) <= 0 {
		return z.set(x)
	}
	if alias(z, x) {
		z = nil
	}

	// 从已知值过大开始，重复“z=⌊（z+⌊x/z⌋)/2.⌋“直到它停止变小。
	// 参见Brent和Zimmermann，现代计算机算法，算法1.13（SqrtInt）。
	// https:
	// 如果x比完美的正方形小一，序列在正确的z和z+1之间振荡；
	// 否则它收敛到正确的z并保持不变。
	var z1, z2 nat
	z1 = z
	z1 = z1.setUint64(1)
	z1 = z1.shl(z1, uint(x.bitLen()+1)/2) // 必须是≥ √x 
	for n := 0; ; n++ {
		z2, _ = z2.div(nil, x, z1)
		z2 = z2.add(z2, z1)
		z2 = z2.shr(z2, 1)
		if z2.cmp(z1) >= 0 {
			// z1是答案。
			// 通过查看循环计数，确定z1或z2当前是否别名为z。
			if n&1 == 0 {
				return z1
			}
			return z.set(z1)
		}
		z1, z2 = z2, z1
	}
}
